package subjectlist;


/**
 * 题目描述：
 * 编辑距离又称Levenshtein距离，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。
 * 许可的编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符。
 * 设计并实现一个算法来计算两个字符串的编辑距离，并计算其复杂度。在某些应用场景下，
 * 替换操作的代价比较高，假设替换操作的代价是插入和删除的2倍，算法该如何调整？
 */
public class T如何求字符串的编辑距离 {

    /**
     * 本题可以使用动态规划的方法来解决，具体思路如下：
     * 给定字符串s1、s2，首先定义一个函数D（i,j）（0＜=i＜=strlen（s1），0＜=j＜=strlen（s2）），
     * 用来表示第一个字符串s1长度为i的子串与第二个字符串s2长度为j的子串的编辑距离。
     * 从s1变到s2可以通过如下三种操作
     *
     * 1）添加操作。假设已经计算出D（i,j-1）的值（s1[0…i]与s2[0…j-1]的编辑距离），
     * 则D（i,j）=D（i,j-1）+1（s1长度为i的字串后面添加s2[j]即可
     *
     * 2）删除操作。假设已经计算出D（i-1,j）的值（s1[0…i-1]到s2[0…j]的编辑距离），
     * 则D（i,j）=D（i-1,j）+1（s1长度为i的字串删除最后的字符s1[j]即可）。
     *
     * 3）替换操作。假设已经计算出D（i-1,j-1）的值（s1[0…i-1]与s2[0…j-1]的编辑距离），
     * 如果s1[i]=s2[j]，则D（i,j）=D（i-1，j-1）；
     * 如果s1[i]!=s2[j]，则D（i,j）=D（i-1,j-1）+1（替换s1[i]为s2[j]，
     * 或替换s2[j]为s1[i]）。
     *
     * 此外，D（0,j）=j且D（i,0）=i（从一个字符串变成长度为0的字符串的代价为这个字符串的长度）。由此可以得出如下实现方式：对于给定的字符串s1、s2，定义一个二维数组D，则有以下几种可能性。
     * 1）如果i==0，那么D[i,j]=j （0＜=j＜=strlen（s2））。
     * 2）如果j==0，那么D[i,j]=i （0＜=i＜=strlen（s1））。
     * 3）如果i＞0且j＞0，
     *  ① 如果s1[i]==s2[j]，那么D （i, j）=min{edit（i-1, j）+1, edit（i, j-1）+1, edit（i-1, j-1）}；
     *  ② 如果s1[i]!=s2[j]，那么D （i, j）=min{edit（i-1, j）+1, edit（i, j-1）+1, edit（i-1, j-1）+1}。
     *
     * 通过以上分析可以发现，对于第一个问题可以直接采用上述的方法来解决。对于第二个问题，由于替换操作是插入或删除操作的2倍，
     * 因此，只需要修改如下条件即可：
     * 如果s1[i]!=s2[j]，那么D （i, j）=min{edit（i-1, j）+1, edit（i, j-1）+1, edit（i-1, j-1）+2}
     */
}
